Sets

Number Sets

N={0,1,2,3...}\Bbb{N}=\{0,1,2,3...\} = set of all natural numbers

Z={...,2,1,0,1,2,3...}\Bbb{Z}=\{...,-2,-1,0,1,2,3...\} = integers

N=Z+={1,2,3...}\Bbb{N}=\Bbb{Z}^+=\{1,2,3...\} = positive integers

R=\Setxx can be represented by a decimal expansion=QQc\Bbb{R}=\Set{x\mid x\ \text{can be represented by a decimal expansion}} = \Bbb{Q}\cup \Bbb{Q}^c = real numbers

Q={p/qp,qZ,q0,p and q have no common factors}\Bbb{Q}=\{p/q\mid p, q\in\Bbb{Z},q\neq 0, p\space and\space q\space have\space no\space common\space factors \} = rational numbers

Qc=Qˉ={xRxQ}\Bbb{Q}^c=\Bbb{\bar{Q}} =\{x\in \Bbb{R}\mid x\notin\Bbb{Q}\} = irrational numbers

C=\setx+igx,yR and i2=1\Bbb{C} =\set{x+ig\mid x,y\in \Bbb{R}\space and\space i^2=-1} = Complex numbers

Intervals

&[a,b]=\{\ x\ |\ a\le x\le b\}\textcolor{hotpink}{\text{ closed interval}}\\ &[a,b)=\{\ x\ |\ a\le x\lt b\}\\ &(a,b]=\{\ x\ |\ a\lt x\le b\}\\ &(a,b)=\{\ x\ |\ a\lt x\lt b\}\textcolor{violet}{\text{ open interval}}\\

Equality

Empty Set

There is a special set that has no elements.

We call this the empty set or null set denoted by \emptyset

Singleton Set
: A set with one element

≢{}\emptyset\not\equiv\{\emptyset\} because thats a singleton set that contains the null set

Venn Diagrams

U
V . a . e . i . o . u

The universal set is denoted by and is represented by the square of the venn diagram

The universal set contains all possible elements

The set VV of all the vowels in the English alphabet can be written as:

V={a,e,i,o,u}V=\{a,e,i,o,u\}

Subsets

Proper Subsets

Remember:     \iff means iff replacing the statement if and only if

AB    x(xAxB)x(xBxA) A\subset B\iff\forall x(x\in A\rightarrow x\in B)\wedge\exists x(x\in B\wedge x\notin A)

Venn Diagram of a Proper Subset

Sets may have other sets as members

U
B
A

Sizes of Set

Let SS be a set. If there are exactly nn distinct elements in SS where nn is a nonnegative integer, we say that SS is a finite set and that nn is the cardinality of SS. The cardinality of SS is denoted by S|S| where S=n|S| = n, we can thus determine that =0|\emptyset|=0

Principle of Inclusion - Exclusion

Let AA and BB be finite sets
Then AB=A+BAB|A\cup B|=|A|+|B| - |A\cap B|

think it terms of sets so we don't double count for the intersection elements

Extended for more than two sets

| A\cup B \cup C| &= A\cup (B \cup C)|\\ & = |A| + |B\cup C| - |A\cap (B \cup C)|\\ & = |A| + |B| + |C| - |B\cap C| - |A\cap (B \cup C)|\color{yellow}{\text{ use distributive law}} \\ & = |A| + |B| + |C| - |B\cap C| - |(A\cap B)\cup (A\cap C)|\\ & = |A| + |B| + |C| - |B\cap C| - |(A\cap B)\cup (A\cap C)|\\ & = |A| + |B| + |C| - |B\cap C| - ||A\cap B| + |A\cap C| - |(A\cap B)\cap (A\cap C)||\\ & = |A| + |B| + |C| - |B\cap C| - |A\cap B| - |A\cap C| + |A\cap B\cap C|\\

Power Sets

Given a set SS, the power set of SS is the set of all subsets of the set SS

The Power set of SS is denoted by P(S)\mathcal{P}(S)

P(A)=\SetBBA\mathcal{P}(A)=\Set{B\mid B\subseteq A}

Cartesian Products

The ordered n-tuple (a1,a2,...,an)(a_1,a_2,...,a_n) is the ordered collection

We say that (a1,...,an)=(b1,...bn) iff(a_1, ... , a_n) = (b_1,...b_n)\ iff\\ a1=b1,a2=b2,...,an=bna_1 = b_1, a_2 = b_2, ..., a_n = b_n or

(i=1,2,...n)(ai=bi)\forall (i = 1, 2, ... n) (a_i = b_i)

Let AA and BB be sets. The Cartesian product of AA and BB, denoted A×BA\times B, is the set of all ordered pairs (a,b)(a,b), where aAa\in A and bBb\in B

A×B=\Set(a,b)aAbBA\times B=\Set{(a,b)|a\in A\wedge b\in B}

The Cartesian product of the sets A1,A2,...AnA_1,A_2, ... A_n denoted by A1×A2×...×AnA_1\times A_2\times ... \times A_n is the set of ordered b-tuples (a1,a2,...,an)(a_1, a_2, ... , a_n) where aia_i belongs to AiA_i for i=1,2,...,ni=1,2,...,n

In other words

A1×A2×...×An=\Set(a1,a2,...,an)aiAi for i=1,2,...,n A_1\times A_2\times ... \times A_n = \Set{(a_1, a_2, ... , a_n)\mid a_i\in A_i\ for\ i=1,2,...,n}

bdg-successFact If Ai=mi|A_i|=m_i then

A1x...xAn=m1m2mn=i=1nmi|A_1x ... xA_n| = m_1 \cdot m_2\cdots m_n = \prod^n_{i=1}m_i

Set Operations

Union of Sets

U
A
B
width="2" height="100"

Let AA and BB be sets. The union of these sets, denoted by ABA\cup B, is the set that contain those elements that are either in AA or BB

AB=\SetxxAxBA\cup B=\Set{x|x\in A\lor x\in B}

Intersection of Sets

U
A
B
width="2" height="100"

Let AA and BB be sets. The intersection of these sets, denoted by ABA\cap B, is the set that contains those elements that are in AA and BB

AB=\SetxxAxBA\cap B=\Set{x|x\in A\wedge x\in B}
Two sets called disjoint if there intersection is the empty set
In other words there is no overlap in the Venn Diagram

Difference of Sets

U
A
B
width="2" height="100"

Let AA and BB be sets. The difference of these sets, denoted by ABA-B, is the set that contains those elements that are in AA but not in BB

AB=\SetxxAxBA-B=\Set{x|x\in A\wedge x\notin B}

Difference between sets AA and BB is sometimes denoted by ABA\setminus B

Compliment of Sets

U
A
B
width="2" height="100"

Let UU be the universal set. The compliment of a set, denoted by Aˉ\bar{A}, is the set that contains those elements that are not in AA thus UAU-A

Aˉ=\SetxU  xA\bar{A}=\Set{x\in U\ |\ x\notin A}

The compliment depends on what we mean by the universal set UU

Set Identities

Equivalence Name
AU=AA\cap U=A
A=AA\cup\emptyset =A
Identity laws
AU=UA\cup U=U
A=A\cap \emptyset =\emptyset
Domination laws
AA=AA\cup A=A
AA=AA\cap A=A
Idempotent laws
Aˉˉ=A\bar{\bar{A}}=A Kind of like double negation right? Complementation law
AB=BAA\cup B=B\cup A
AB=BAA\cap B=B\cap A
Commutative laws
A(BC)=(AB)CA\cup(B\cup C)=(A\cup B)\cup C
A(BC)=(AB)CA\cap(B\cap C)=(A\cap B)\cap C
Associative laws
A(BC)=(AB)(AC)A\cup(B\cap C)=(A\cup B)\cap(A\cup C)
A(BC)=(AB)(AC)A\cap(B\cup C)=(A\cap B)\cup(A\cap C)
Distributive laws
AB=AˉB\overline{A\cap B}=\bar{A}\cup\overline{B}
AB=AˉBˉ\overline{A\cup B}=\bar{A}\cap\bar{B}
De Morgan's Laws
A(AB)=AA\cup(A\cap B)=A
A(AB)=AA\cap(A\cup B)=A
Absorption laws
AAˉ=UA\cup\bar{A}=U
AAˉ=A\cap\bar{A}=\emptyset
Complement laws

Proof of Demorgan's law for sets

Arbitrary Unions or Intersections

We can define arbitrary unions and intersections for a finite number of sets

A_1\cap A_2\cap\cdots\cap A_n&=\Set{x\mid x\in A_i\text{ for all }i=1,\cdots ,n}\\ A_1\cup A_2\cup\cdots\cup A_n&=\Set{x\mid x\in A_i\text{ for some }i=1,\cdots ,n}\\

Demorgan's Laws become

\overline{A_1\cup A_2\cup\cdots\cup A_n}&=\bar{A_1}\cap \bar{A_2}\cap\cdots\cap \bar{A_n}\\ \overline{A_1\cap A_2\cap\cdots\cap A_n}&=\bar{A_1}\cup \bar{A_2}\cup\cdots\cup \bar{A_n}\\

Set Operations via Bit Strings

Consider U=\Set1,2,3,4,5,6,7,8,9,10U=\Set{1,2,3,4,5,6,7,8,9,10}

Each subset of UU can be represented as a bit string of length 10, where AUA\subseteq U is associated to the bit string Bit10(A)=(b1,b2,b3,b5,b4,b5,b6,b7,b8,b9,b10)Bit_{10}(A)=(b_1,b_2,b_3,b_5,b_4,b_5,b_6,b_7,b_8,b_9,b_{10})

where bi=1 if iAb_i = 1\ if\ i\in A and 0 if iA0\ if\ i\notin A

For each bit string of length 10 there is a subset of UU and for each subset of UU there is a bit string of length 10

We say there is a one-to-one corresponded between bitstrings of length 10 and the subsets of a set with 10 elements

(0,,0)(0,\cdots ,0)\leftrightarrow\emptyset
(1,,1)U(1,\cdots ,1)\leftrightarrow U

So if A=\Set2,3,7,8,10A=\Set{2,3,7,8,10}

Bit10(A)=\Set0,1,1,0,0,0,1,1,0,1Bit_{10}(A)=\Set{0,1,1,0,0,0,1,1,0,1}